package com.wtgroup.demo.mianshi.算法.二叉树;

import com.wtgroup.demo.mianshi.算法.二叉树.model.CompleteBinTree;
import com.wtgroup.demo.mianshi.算法.二叉树.model.Node;
import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author L&J
 * @version 0.0.0
 * @email liuhejun108@163.com
 * @date 2019/9/7 22:28
 */
public class 完全二叉树 {
    /*
    * 自上而下, 自左向右 编号
    *
    * i 的双亲 i/2 ,
    *
    * 非完全二叉树, 需要添加一些空节点, 以便顺序存储.
    * 但浪费空间. 故一般顺序存储只用于完全二叉树.
    *
    * 非完全二叉树, 可以用链式存储结构.
    * 数据域, 左,右指针域. 二叉链表.
    * 三叉链表, 增加parent指针.
    *
    * 广度优先遍历(层次)
    * 深度优先遍历(前序,后序,中序)
    * */

    /*
    * 广度优先遍历(BFS)
    * 1. 根节点入队
    * 2. 循环:
    *   出队 -> 打印 -> 子节点入队
    * */

    @Test
    public void 广度优先遍历(){
        List<String> strings = Arrays.asList("A", "B", "C", "D", "E", "F");
        CompleteBinTree<String> binTree = new CompleteBinTree<String>(strings);

        // System.out.println(binTree);

        LinkedList<Node> queue = new LinkedList<Node>();

        Node<String> root = binTree.getRoot();
        queue.addLast(root);
        while ( !queue.isEmpty() ) {
            Node first = queue.poll();
            System.out.println(first);
            if ( first.getLeft() != null ) {
                queue.offer(first.getLeft());
            }
            if ( first.getRight() != null ) {
                queue.offer(first.getRight());
            }
        }
    }


}
